package DP.子序列;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;

/*
    825:思路
            按最上被压的纸牌排序(二分
            没找到：直接最右开新堆，不用有序！
            最后res=总堆数
 */
/*
包含全细节的例子 -> 010323
[0,1,0,3,2,3]
0 1 3 3
0

易错点：
    0 全程不用nums[l] (只有最后用一次nums[l]

    1 if h[m] 不是 nums[l]

    2 找左边界 就一个==t r反 , 后面出来都是l
*/
public class 最长递增子序列300_纸牌法 {
    
    @Test
    public void test() {
        int[] p = {3,1,2};
        lengthOfLIS(p);
    }

    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] h = new int[n];
        //初始化 有0是真值，不能全0 (eg.010323
        for (int k = 0; k < n; k++) {
            h[k] = 10001;
        }
        //压纸牌
        h[0] = nums[0];
        int hnext = 1;
        for (int i = 1; i < n; i++) {
            int l=0,r=i-1,t=nums[i];
            while(l<=r){
                int m=l+(r-l)/2;
                if(h[m]<t){
                    l=m+1;
                }else if(h[m]>=t){
                    r=m-1;
                }
            }
//            if(l==n || nums[l]<t){
            if(l==n || h[l]<t){
                h[hnext++] = nums[i];
            }
            else {
                h[l]=nums[i];
            }
        }
        //统计堆数
        int hcount = 0;
        for (int i = 0; i < n; i++) {
            if (h[i] != 10001) {
                hcount++;
            }
        }
        return hcount;
    }
}
